package _11_整理题目._6_模拟设计._原地hash;

import org.junit.Test;

/**
 * 找出数组中重复的数字。
 *
 * 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。
 * 数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。
 * 请找出数组中任意一个重复的数字。
 *
 */
public class RepeatNum {
    /**
     * 校验每个 位置i 是否 对应值 nums[i]
     * 如果不等于：则循环交换，直至 i == nums[i]
     *      有重复值的条件： nums[i] == nums[nums[i]]
     *      交换 nums[i] nums[nums[i]]
     */
    public int findRepeatNumber(int[] nums) {
        for(int i = 0;i<nums.length;i++){
            while(i != nums[i]){
                if( nums[i] == nums[nums[i]] ) return nums[i];
                int temp = nums[nums[i]];
                nums[nums[i]]=nums[i];
                nums[i]=temp;
            }
        }
        return -1;
    }

    public int findRepeatNumber2(int[] nums) {
        int i = 0;
        while (i < nums.length) {
            if (i == nums[i]) {
                i++;
            } else {
                if (nums[i] == nums[nums[i]]) {
                    return nums[i];
                } else {
                    int tmp = nums[nums[i]];
                    nums[nums[i]] = nums[i];
                    nums[i] = tmp;
                }
            }
        }
        return -1;
    }

    @Test
    public void main() {
        int[] arr = {2, 3, 1, 0, 2, 5, 3};
        System.out.println(findRepeatNumber(arr));

    }


}
